package com.dy.树.二叉树的层序遍历;

import com.dy.树.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/*
二叉树的层次遍历
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> res = new ArrayList<>();
        if(root==null)return res;
        Queue<TreeNode> q = new LinkedList<>();

        q.add(root);
        while(!q.isEmpty()){
            int count = q.size();
            List<Integer> list=new ArrayList();

            while(count>0){
                TreeNode r = q.peek();
                q.poll();
                list.add(r.val);
                if(r.left!=null) q.add(r.left);
                if(r.right!=null) q.add(r.right);
                count--;
            }
            res.add(list);

        }
        return res;

    }
    /*
    递归
     */
    private List<List<Integer>> result = new ArrayList();
    public List<List<Integer>> levelOrder2(TreeNode root) {
        helper(1,root);
        return result;
    }

    private void helper(int height,TreeNode root){
        if(root == null){
            return;
        }
        //将当前结点添加进去
        if(height > result.size()){
            result.add(new ArrayList());
        }
        List<Integer> eachHeight = result.get(height-1);
        eachHeight.add(root.val);
        //子树
        helper(height+1,root.left);
        helper(height+1,root.right);
    }
}
